home *** CD-ROM | disk | FTP | other *** search
/ Trading on the Edge / Trading On The Edge - CD-ROM Toolkit (Wayzata Technology)(2031)(1994).bin / pc / mac_file / vendor_d / ga_softw / ooga / how-to.lis < prev    next >
File List  |  1991-02-03  |  11KB  |  389 lines
  1. ;;; -*- Mode:Lisp; Package:OOGA; Base:10; Syntax:COMMON-LISP -*-
  2. #||
  3.             RESTRICTED RIGHTS LEGEND
  4.                     
  5.  Use, duplication, or disclosure by the Government is subject to
  6.  restrictions as set forth in subdivision (b)(3)(ii) of the Rights in
  7.  Technical Data and Computer Software Clause at 52.227-7013 of the DOD
  8.  FAR Supplement.
  9.                     
  10.                 TSP (The Software Partnership)
  11.                 P.O. Box 991
  12.                 Melrose, MA 02176
  13.                     
  14.       Copyright 1990 by Lawrence Davis and Daniel Cerys, all rights reserved.
  15. ||#
  16.  
  17. (in-package :ooga)
  18.  
  19. #|
  20.  
  21. This file contains routines for using the traditional genetic algorithm
  22. to optimize a function of your own.
  23.  
  24. |#
  25.  
  26.  
  27. ;************************************************************
  28.  
  29. ;    EXAMPLE  1:  USING THE TRADITIONAL GENETIC ALGORITHM
  30.  
  31.  
  32. ;;; The following expressions create a genetic
  33. ;;; algorithm that maximizes the sum of the chromosome bits.
  34. ;;; The optimal chromosome will consist entirely of ones.
  35.  
  36.  
  37. ;;; STEP 1
  38.  
  39. ;;; Describe the one vector genetic algorithm
  40. (defclass ONE-VECTOR-GENETIC-ALGORITHM (traditional-ga) ())
  41.  
  42.  
  43. ;;; STEP 3
  44.  
  45.  
  46. ;;; Describe the sum vector evaluator
  47. (defclass SUM-VECTOR-EVALUATOR (evaluator) ())
  48.  
  49.  
  50. ;;; Describe the sum vector evaluation function.  It sums the
  51. ;;; chromosome fields.
  52. (defmethod EVALUATE-MEMBER
  53.        ((evaluator sum-vector-evaluator)
  54.         (population-member population-member))
  55.     (apply '+ (chromosome population-member)))
  56.  
  57.  
  58. ;;; STEP 5
  59.  
  60. ;;; Describe the particulars of this algorithm
  61. (def-append-method GET-PARTICULARS ((ga one-vector-genetic-algorithm))
  62.     `((evaluator ,(make-instance 'sum-vector-evaluator))
  63.       (population-size 50)
  64.       (desired-trials 1600)
  65.       (bit-string-length 30)))
  66.  
  67.  
  68. ;;; use (trial-run 'one-vector-genetic-algorithm) to run this
  69. ;;; GA.
  70.  
  71.  
  72. ;************************************************************
  73.  
  74. ;    EXAMPLE  2:  USING THE TRADITIONAL GENETIC ALGORITHM
  75.  
  76.  
  77. ;;; The following expressions create a genetic
  78. ;;; algorithm that minimizes the sum of the chromosome bits.
  79. ;;; The optimal chromosome will consist entirely of zeros.
  80. ;;; Because we are minimizing, we should define a new class of
  81. ;;; population member and a new evaluation-better-p method.
  82.  
  83. ;;; STEP 1
  84.  
  85. ;;; Describe zero vector genetic algorithm
  86. (defclass ZERO-VECTOR-GENETIC-ALGORITHM (traditional-ga) ())
  87.  
  88.  
  89. ;;; STEP 2
  90.  
  91. ;;; Describe zero vector population member class
  92. (defclass ZERO-VECTOR-POPULATION-MEMBER (population-member) ())
  93.  
  94.  
  95. ;;; Minimize instead of maximizing
  96. (defmethod EVALUATION-BETTER-P ((member1 zero-vector-population-member)
  97.                 (member2 zero-vector-population-member))
  98.   "Non-default behavior: lower evaluation values are better."
  99.   (< (evaluation member1) (evaluation member2)))
  100.  
  101.  
  102. ;;; STEP 3
  103.  
  104. ;;; Describe zero vector evaluator
  105. (defclass ZERO-VECTOR-EVALUATOR (evaluator) ())
  106.  
  107.  
  108. ;;; Describe zero vector evaluation function.  It sums the
  109. ;;; chromosome fields.  (This is the same method as the
  110. ;;; evaluator above.)
  111. (defmethod EVALUATE-MEMBER
  112.        ((evaluator zero-vector-evaluator) zero-vector-population-member)
  113.     (apply '+ (chromosome zero-vector-population-member)))
  114.  
  115.  
  116. ;;; STEP 5
  117.  
  118. ;;; Tell OOGA the zero vector ga particulars
  119. (defmethod GET-PARTICULARS append
  120.        ((ga zero-vector-genetic-algorithm))
  121.     `((population-size 50)
  122.       (desired-trials 1600)
  123.       (bit-string-length 30)
  124.       (evaluator ,(make-instance 'zero-vector-evaluator))
  125.       (population-member-class zero-vector-population-member))
  126.     )
  127.  
  128.  
  129. ;;; use (trial-run 'zero-vector-genetic-algorithm) to run this
  130. ;;; GA.
  131.  
  132.  
  133. ;************************************************************
  134.  
  135. ;    EXAMPLE 3:  USING THE STEADY-STATE GENETIC ALGORITHM
  136.  
  137.  
  138. ;;; The following expression creates a steady-state genetic algorithm
  139. ;;; that minimizes the function used above, much faster from the point
  140. ;;; of view of total evaluations.  This way of doing it by using
  141. ;;;  a component class requires much less code on the user's part.
  142.  
  143. ;;; Note that the order of the component classes here is
  144. ;;; important.  If the order were reversed, the steady-state
  145. ;;; methods would not replace the traditional ga methods.
  146.  
  147.  
  148. ;;; STEP 1
  149.  
  150. (defclass STEADY-STATE-ZERO-VECTOR-GA
  151.       (steady-state-ga
  152.         zero-vector-genetic-algorithm)())
  153.  
  154.  
  155. ;;; use (trial-run 'steady-state-zero-vector-ga) to run this
  156. ;;; GA.
  157.  
  158.  
  159. ;************************************************************
  160.  
  161. ;    EXAMPLE 4:  USING THE REAL-VALUED GENETIC ALGORITHM
  162.  
  163. ;;; The following expressions create a real-valued genetic
  164. ;;; functionally equivalent to GA 5-1, except that now we use
  165. ;;; the real-valued-genetic-algorithm as a component class.  
  166. ;;; We alter the parameters of the operators by altering
  167. ;;; the probability values, mutation, and creep specs.  These
  168. ;;; changes are for illustration purposes only; they degrade the
  169. ;;; performance of the genetic algorithm.
  170.  
  171. ;;; The real-value-f6 evaluator has already been defined.
  172.  
  173.  
  174. ;;; STEP 1
  175.  
  176. ;;; Describe this GA.
  177. (defclass REAL-VALUED-F6-GA
  178.       (advanced-techniques-genetic-algorithm
  179.        real-value-genetic-algorithm) ())
  180.  
  181.  
  182. ;;; Describe the particulars.  This function is created by
  183. ;;; copying the corresponding function in the definition of the
  184. ;;; real-value-genetic-algorithm, modifying the parameter
  185. ;;; values, and adding the evaluator, parent selection
  186. ;;; technique, and fitness technique particulars to finish the
  187. ;;; description of the GA, and then specifying the other
  188. ;;; particulars that complete the GA.
  189.  
  190.  
  191. ;;; STEP 5
  192.  
  193. (def-append-method GET-PARTICULARS ((ga real-valued-f6-ga))
  194.  
  195.     ;;;THESE PARTICULARS ARE COPIED FROM THE
  196.     ;;;REAL-VALUE-GENETIC-ALGORITHM DEFINITION, BUT PARAMETER
  197.     ;;;VALUES ARE MODIFIED.
  198.     `((representation-technique
  199.     ,(make-instance 'real-number-representation
  200.             :real-number-specs '((0 4194303 t))
  201.             :chromosome-length 2))
  202.       (initialization-technique
  203.     ,(make-instance 'random-real-number-initialization))
  204.       (operator-list
  205.     ,(list (make-instance 'uniform-list-crossover)
  206.            (make-instance 'average-real-crossover)  
  207.            (make-instance 'real-number-mutation
  208.                   :mutation-rate .6
  209.                   :mutation-specs '((0 4194303 t)))
  210.            (make-instance 'real-number-creep
  211.                   :creep-rate .7
  212.                   :creep-specs '((100000 t)))
  213.            (make-instance 'real-number-creep
  214.                   :creep-rate .5
  215.                   :creep-specs '((5000 t)))))
  216.       (operator-weights ,(list 10 40 10 30 10))
  217.       (reproduction-parameterization-techniques
  218.     ,(list (make-instance
  219.          'interpolate-operator-weights
  220.          :interpolation-specs
  221.          '((10 40 10 30 10) (10 20 0 40 30)))))
  222.       
  223.       ;;;THESE PARTICULARS ARE SPECIFIC TO THIS GA
  224.       (evaluator ,(make-instance 'real-number-f6))
  225.       (population-size 100)
  226.       (desired-trials 4000)))
  227.  
  228.  
  229. ;;; use (trial-run 'real-valued-f6-ga) to run this
  230. ;;; GA.
  231.  
  232. ;************************************************************
  233.  
  234. ;    EXAMPLE 5:  USING THE ORDER-BASED GENETIC ALGORITHM
  235.  
  236. ;;; The following expressions create an order-based genetic
  237. ;;; algorithm that attempts to evolve a sorting of the elements
  238. ;;; of a 50-member list.
  239.  
  240.  
  241. ;;; STEP 1
  242.  
  243. ;;; Define the genetic algorithm
  244. (defclass SORTING-GENETIC-ALGORITHM
  245.       (advanced-techniques-genetic-algorithm
  246.         order-based-genetic-algorithm) ())
  247.  
  248.  
  249. ;;; STEP 2
  250.  
  251. ;;; We are minimizing.
  252. (defclass SORTING-POPULATION-MEMBER (population-member)())
  253.  
  254. (defmethod EVALUATION-BETTER-P
  255.        ((member1 sorting-population-member)
  256.         (member2 sorting-population-member))
  257.   (< (evaluation member1) (evaluation member2)))
  258.  
  259.  
  260. ;;; Describe the display method for this type of population member
  261. (defmethod DISPLAY-MEMBER
  262.        ((representation-technique permuted-list)
  263.         (population-member sorting-population-member))
  264.   (format *standard-output* "~%")
  265.   (format *standard-output* "  ~a" (evaluation population-member))
  266.   (loop for node in (firstn 30 (chromosome population-member))
  267.     do (format *standard-output* " ~a" node))
  268.   )
  269.  
  270.  
  271. ;;; STEP 3
  272.  
  273. ;;;The evaluator
  274. (defclass SORTING-EVALUATOR (evaluator) ())
  275.  
  276.  
  277. (defmethod EVALUATE-MEMBER
  278.        ((evaluator sorting-evaluator)
  279.         (member sorting-population-member))
  280.   "Promote a sorted list"
  281.   (loop for n from 1
  282.     for value in (chromosome member)
  283.     summing (abs (- n value))))
  284.  
  285.  
  286. (defmethod LIST-TO-PERMUTE ((evaluator sorting-evaluator))
  287.   (loop for n from 1 to 50 collect n))
  288.  
  289.  
  290. ;;; STEP 5
  291.  
  292. (def-append-method GET-PARTICULARS ((ga sorting-genetic-algorithm))
  293.     `((population-size 100)
  294.       (desired-trials 6000)
  295.       (population-member-class sorting-population-member)
  296.       (evaluator ,(make-instance 'sorting-evaluator))))
  297.  
  298.  
  299. ;;; use (trial-run 'sorting-genetic-algorithm) to run this
  300. ;;; GA.
  301.  
  302.  
  303.  
  304. ;************************************************************
  305.  
  306. ;    EXAMPLE 6:  USING THE ADAPTIVE TECHNIQUES
  307.  
  308.  
  309. ;;; 
  310.  
  311.  
  312.  
  313. ;;; The following expressions derive operator weights for the
  314. ;;; genetic algorithm just described.  The process of creating
  315. ;;; an adaptive genetic algorithm is more complicated than that
  316. ;;; of creating the previous types of genetic algorithms.  Read
  317. ;;; the documentation carefully.
  318.  
  319.  
  320. ;;; STEP 1
  321.  
  322. ;;; Define the genetic algorithm.  Note that the population and
  323. ;;; reproduction modules are installed here rather than with the
  324. ;;; install-particulars process.  These modules should be in
  325. ;;; place before the install-particulars process begins, so that
  326. ;;; they are available to receive the particular techniques.  If
  327. ;;; they were installed as part of the particulars list for the
  328. ;;; adaptive-sorting-genetic-algorithm, they would be installed
  329. ;;; last, and the previously-installed particulars would be
  330. ;;; lost.
  331. (defclass ADAPTIVE-SORTING-GENETIC-ALGORITHM
  332.       (sorting-genetic-algorithm
  333.         adapt-initial-operator-weights) ()
  334.     (:default-initargs
  335.        :population-module (make-instance
  336.                 'adaptive-sorting-population-module)
  337.        :reproduction-module (make-instance
  338.                   'adaptive-sorting-reproduction-module)))
  339.  
  340.  
  341.  
  342.  
  343. ;;; Define the population module.  It must be installed before
  344. ;;; the particulars are installed.  It must have some new
  345. ;;; component classes in order to carry out adaptation
  346. ;;; correctly.
  347. (defclass ADAPTIVE-SORTING-POPULATION-MODULE
  348.       (trace-operator-weights
  349.          adaptive-operator-module
  350.         basic-population-module)
  351.      ())
  352.  
  353.  
  354. ;;; Define the reproduction module.  It must have the
  355. ;;; adaptive-reproduction-module class as a component.
  356. (defclass ADAPTIVE-SORTING-REPRODUCTION-MODULE
  357.       (adaptive-reproduction-module) ())
  358.  
  359.  
  360. (def-append-method GET-PARTICULARS ((ga adaptive-sorting-genetic-algorithm))
  361.     `((population-member-class adaptive-sorting-population-member)
  362.       (reproduction-parameterization-techniques nil)
  363.       (initial-operator-weights (70 30))))
  364.  
  365.  
  366. ;;; STEP 2
  367.  
  368. ;;; Define the population member.  It must have the
  369. ;;; adaptation-population-member class as a component.
  370. (defclass ADAPTIVE-SORTING-POPULATION-MEMBER
  371.       (sorting-population-member
  372.         adaptation-population-member)
  373.     ())
  374.  
  375.  
  376. ;;; Now the algorithm is ready to run.  To have it find initial
  377. ;;; operator weights, run the function
  378. ;;; (find-initial-operator-weights 
  379. ;;;     (make-instance 'adaptive-sorting-genetic-algorithm))
  380.  
  381. ;;; With the new initialization algorithm, the weights found
  382. ;;; tend to lie near (80 20), rather than the default value of
  383. ;;; (70 30).
  384.  
  385.  
  386. ;;; To see the algorithm adapt weights, run the function
  387. ;;; (trial-run 'adaptive-sorting-genetic-algorithm).
  388.  
  389.